1. Field of the Invention
The invention described herein relates to computer graphics, and more particularly to modeling and manipulation of three dimensional surfaces.
2. Related Art
Currently, subdivision surfaces are not widely used in surface design, especially in the high-end design market, such as the automotive industry where surfaces of degree 5 and 7 are frequently used in the modeling of body panels. Such surfaces are important because they give designers enough degrees of freedom to directly control reflection lines in the panels. The main problem these designers currently face is in the manipulation of regions of irregular topology. For example, corners are typically handled by trimming three non-uniform rational B-spline (NURBS) surfaces of high degree. Trimming is a time-consuming process that yields only approximate continuity. Indeed, at the trim the surface may not even be C0 continuous. Consequently, designers are forced to fine-tune many arcane parameters for the best fit.
Generalizations for uniform B-spline surfaces of degrees two and three were published in 1978 simultaneously by Catmull and Clark (Catmull, E., and Clark, J., Computer Aided Design 10:350-355 (1978)) and by Doo and Sabin (Doo, D., and Sabin, M. A., Computer Aided Design 10:356-360(1978)). Since then, it seems no attempt has been successful in extending this work to surfaces of higher degrees. This is partly due to the belief that such methods require large subdivision masks and, consequently, would be difficult to implement. Lower-degree surfaces are sufficient for character animation and free-form modeling, which have up to now been the primary applications of subdivision surfaces in industry.
What is needed, therefore, is a method for generalizing uniform B-spline surfaces of higher degree. A method for doing so must create surfaces that are naturally curvature-continuous at as many points as possible, minimizing the number of points where the curvature generally diverges. This would minimize the need for trimming. Note that by using the higher-degree surfaces, the rate of divergence can be reduced. Moreover, such a method should be easy to implement and should not require large subdivision masks.
The invention described herein is a method and computer program product for converting an arbitrary mesh to a subdivision surface. Where the subdivision surface is to have an odd degree d=2m+1 on the regular part of the mesh, the method includes the steps of subdividing the mesh in a linear fashion, then iteratively smoothing the subdivided mesh m times. Where the subdivision surface is to have an even degree d=2m on the regular part of the mesh, the method includes the steps of subdividing the mesh, calculating the dual of the subdivided mesh, and iteratively smoothing the dual mxe2x88x921 times. In either case, the resulting subdivision surfaces generalize uniform tensor product B-spline surfaces of any degree to meshes of arbitrary topology. The method uses subdivision rules that involve direct neighbors, and is computationally efficient.
Although these generalizations are not C2 everywhere, they provide useful alternatives to the current practice in the high end design market. The method offers Cdxe2x88x921 continuity everywhere except at the irregular points where they are C1. This continuity compares favorably with trimmed NURBS, which are often not even C0. While the curvature, in general, diverges at the irregular points, it does so very slowly.